ABSTRACT
Unlike traditional routing schemes that route all traffic along a single path, multipath routing strategies split the traffic
among several paths in order to ease congestion. It has been widely recognized that multipath routing can be
fundamentally more efficient than the traditional approach of routing along single paths. Yet, in contrast to the singlepath routing approach, most studies in the context of multipath routing focused on heuristic methods. We demonstrate
the significant advantage of optimal (or near optimal) solutions. Hence, we investigate multipath routing adopting a
rigorous (theoretical) approach. We formalize problems that incorporate two major requirements of multipath routing.
Then, we establish the intractability of these problems in terms of computational complexity. Finally, we establish
efficient solutions with proven performance guarantees.
Keywords: - Congestion Avoidance, Multi path routing, NP-hard, Quality of Service, Routing protocols